package hot100;

import DTO.TreeNode;

public class lowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件：如果当前节点为 null，或者等于 p 或 q，直接返回当前节点
        if (root == null || root == p || root == q) {
            return root;
        }

        // 递归查找左子树和右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果左子树没有找到 p 或 q，说明 LCA 在右子树
        if (left == null) {
            return right;
        }
        // 如果右子树没有找到 p 或 q，说明 LCA 在左子树
        if (right == null) {
            return left;
        }
        // 如果左右子树都找到了 p 和 q，说明当前节点 root 就是 LCA
        return root;
    }
}
